package com.sise.Linked;


/**
 *      707. 设计链表(双链表)
 */
public class _707_MyLinkedList_02 {
    int size;
    DoublyListNode head, tail;

    _707_MyLinkedList_02() {
        size = 0;
        head = new DoublyListNode(0);
        tail = new DoublyListNode(0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        DoublyListNode cur = head;

        // 通过判断 index < (size - 1) / 2 来决定从头结点还是从尾结点遍历，提高效率
        if (index < (size - 1) / 2) {
            for (int i = 0; i <= index; i++) {
                cur = cur.next;
            }
        } else {
            cur = tail;
            for (int i = 0; i <= size - index - 1; i++) {
                cur = cur.prev;
            }
        }

        return cur.val;
    }

    public void addAtHead(int val) {
        DoublyListNode cur = head;
        DoublyListNode newNode = new DoublyListNode(val);
        newNode.next = cur.next;
        cur.next.prev = newNode;
        cur.next = newNode;
        newNode.prev = cur;
        size++;
    }

    public void addAtTail(int val) {
        DoublyListNode cur = tail;
        DoublyListNode newNode = new DoublyListNode(val);
        cur.prev.next = newNode;
        newNode.prev = cur.prev;
        newNode.next = tail;
        cur.prev = newNode;
        size++;
    }

    // 直接遍历到该位置，直接添加即可
    public void addAtIndex(int index, int val) {
        if (index > size) return;
        if (index < 0) index = 0;
        DoublyListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        DoublyListNode newNode = new DoublyListNode(val);
        newNode.next = cur.next;
        cur.next.prev = newNode;
        cur.next = newNode;
        newNode.prev = cur;
        size++;
    }

    public void deleteAtIndex(int index) {
        if (index >= size || index < 0) return;
        DoublyListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.next.next.prev = cur;
        cur.next = cur.next.next;
        size--;
    }
}

class DoublyListNode {

    int val;
    DoublyListNode next;
    DoublyListNode prev;

    DoublyListNode(int x) {
        val = x;
    }
}
